package base.map.findPath
{
	import flash.geom.Point;

	public class FindPath
	{
		/**
		 *单元格子大小 
		 */		
		private var _cellSize:int;
		
		/**
		 *寻路导航网格节点集 
		 */		
		private var _findPathNodes:Vector.<FindPathNode>;
		
		/**
		 *已经寻到的导航网格集 
		 */		
		private var _findPaths:Vector.<FindPathNode>=new Vector.<FindPathNode>();
		
		/**
		 *寻到的的路径点列表 
		 */		
		private var _path:Vector.<Point>=new Vector.<Point>();;
		
		/**
		 *开始节点 
		 */		
		private var _startNode:FindPathNode;
		
		/**
		 *结束节点 
		 */		
		private var _endNode:FindPathNode;
		/**
		 *最大跨越通行地形高度 
		 */		
		private var _walkableHeight:int;
		
		/**
		 *最大穿越通行地形高度 
		 */		
		private var _walkableBottom:int;
		
		private var _diagCost:Number = Math.SQRT2;
		private var _straightCost:Number = 1.0;
		
		public function FindPath(findPathNodes:Vector.<FindPathNode>, cellSize:int, walkableHeight:int, walkableBottom:int)
		{
			_findPathNodes=findPathNodes;
			_cellSize=cellSize;
			_walkableHeight=walkableHeight;
			_walkableBottom=walkableBottom;
		}
		
		private var _openNodes:Array=[];
		private var _closedNodes:Array=[];
		/**
		 *进行寻路，并生成寻到的的路径点列表
		 * @return 如果可寻路则返回true,不可寻路返回false
		 * 
		 */		
		public function findPath(startPoint:Point, endPoint:Point):Boolean
		{
			var startCell:FindPathCell=new FindPathCell();
			var endCell:FindPathCell=new FindPathCell();
			startCell.x=startPoint.x/_cellSize;
			startCell.y=startPoint.y/_cellSize;
			endCell.x=endPoint.x/_cellSize;
			endCell.y=endPoint.y/_cellSize;
			_startNode=getFindPathNodeByCell(startCell);
			_endNode=getFindPathNodeByCell(endCell);
			
			if(_startNode==null || _endNode==null)
			{
				trace("没找到路径");
				return false;
			}
			_startNode.enterCell=startCell;
			_endNode.enterCell=endCell;
			
			if(_startNode==_endNode)
			{//如果起始节点等于终节点，就返回直接点
				buildPath(startPoint, endPoint, _startNode, _endNode);
				return true;
			}
			
			_startNode.g=0;
			_startNode.h = heuristic(_startNode);
			_startNode.f = _startNode.g + _startNode.h;
			
			var node:FindPathNode=_startNode;
			var enterCell:FindPathCell;
			while(node != _endNode)
			{
				for each(var testNode:FindPathNode in node.linkNodes)
				{
					if(isClosed(testNode))continue;
					enterCell=new FindPathCell();
					if(testNode.x+testNode.width-1<node.enterCell.x)
					{
						enterCell.x=testNode.x+testNode.width-1;
					}
					else if(testNode.x>node.x)
					{
						enterCell.x=testNode.x;
					}
					else
					{
						enterCell.x=node.enterCell.x;
					}
					
					if(testNode.y+testNode.height-1<node.enterCell.y)
					{
						enterCell.y=testNode.y+testNode.height-1;
					}
					else if(testNode.y>node.y)
					{
						enterCell.y=testNode.y;
					}
					else
					{
						enterCell.y=node.enterCell.y;
					}
					testNode.enterCell=enterCell;
					
					var c:Number=cost(node, testNode);
					var g:Number = node.g + c * testNode.costMultiplier;
					var h:Number = heuristic(testNode);
					var f:Number = g + h;
					
					if(isOpen(testNode))
					{
						if(testNode.f > f)
						{
							testNode.f = f;
							testNode.g = g;
							testNode.h = h;
							testNode.parent = node;
						}
					}
					else
					{
						testNode.f = f;
						testNode.g = g;
						testNode.h = h;
						testNode.parent = node;
						_openNodes.push(testNode);
					}
				}
				
				_closedNodes.push(node);
				if(_openNodes.length == 0)
				{
					trace("没找到路径");
					return false
				}
				_openNodes.sortOn("f", Array.NUMERIC);
				node = _openNodes.shift() as FindPathNode;
			}
			buildPath(startPoint, endPoint, _startNode, _endNode);
			return true;
		}
		
		/**
		 * 生成寻到的的路径点列表
		 * 
		 */		
		private function buildPath(startPoint:Point, endPoint:Point, startNode:FindPathNode, endNode:FindPathNode):void
		{
			var node:FindPathNode = _endNode;
			_findPaths.push(node);
			while(node && node != _startNode)
			{
				node = node.parent;
				if(node)_findPaths.unshift(node);
			}
			
			if(_findPaths.length<=0)return;
			_path.push(startPoint.clone());
			if(_findPaths.length==1)
			{//路径节点只有一个时，说明起点与终点在同一个寻路网格里
				_path.push(endPoint.clone());
				return;
			}
			
			_findPaths.shift();
			var edegPoint1:Point;//当前寻路网格的临边点1
			var edegPoint2:Point;//当前寻路网格的临边点2
			var linePoint1:Point;//当前拐点1
			var linePoint2:Point;//当前拐点2
			for each(var findPathNode:FindPathNode in  _findPaths)
			{
				
//				var pX:int;
//				var pY:int;
//				if(findPathNode==endNode)
//				{
//					pX=endPoint.x;
//					pY=endPoint.y;
//				}
//				else
//				{
//					pX=findPathNode.enterCell.x*_cellSize+_cellSize/2;
//					pY=findPathNode.enterCell.y*_cellSize+_cellSize/2;
//				}
//				_path.push(new Point(pX, pY));
			}
		}
		
		/**
		 *估价计算方法 
		 * @param findPathNode
		 * @return 
		 * 
		 */		
		private function heuristic(findPathNode:FindPathNode):Number
		{
			var dx:Number = Math.abs(findPathNode.enterCell.x - _endNode.enterCell.x);
			var dy:Number = Math.abs(findPathNode.enterCell.y - _endNode.enterCell.y);
			var diag:Number = Math.min(dx, dy);
			var straight:Number = dx + dy;
			return _diagCost * diag + _straightCost * (straight - 2 * diag);
		}
		
		/**
		 *代价计算方法  
		 * @param node 当前起始节点
		 * @param testNode 代价计算的节点
		 * @return 
		 * 
		 */			
		private function cost(node:FindPathNode, testNode:FindPathNode):Number
		{
			var costValue:Number=0;//=Point.distance(new Point(testNode.x, testNode.y), new Point(testNode.x+testNode.width-1, testNode.y+testNode.height-1));
			//判定测试节点位于终节点方向位置
			if(testNode.y+testNode.height-1<_endNode.y)
			{//位于终节点上方
				costValue=testNode.height-testNode.enterCell.y;
//				//判定当前节点位于测试点方向位置
//				if(node.x+node.width-1>=testNode.x && node.y+node.height-1<testNode.y)
//				{//当前节点位于测试节点上方
//					costValue=testNode.height;
//				}
//				else if(node.x+node.width-1>=testNode.x && node.y>testNode.y+testNode.height-1)
//				{//当前节点位于测试节点下方
//					costValue=testNode.width;
//				}
			}
			else if(testNode.y>_endNode.y+_endNode.height-1)
			{//位于终节点下方
				costValue=testNode.enterCell.y-testNode.y;
			}
			else if(testNode.x+testNode.width-1<_endNode.x)
			{//位于终节点左方
				costValue=testNode.x+testNode.width-testNode.enterCell.x;
			}
			else if(testNode.x>_endNode.x+_endNode.width-1)
			{//位于终节点右方
				costValue=testNode.enterCell.x-testNode.x;
			}
			costValue+=Point.distance(new Point(node.enterCell.x, node.enterCell.y), new Point(testNode.enterCell.x, testNode.enterCell.y));
			return costValue;
		}
		
		/**
		 *是否在待考察列表里面 
		 * @param findPathNode
		 * @return 
		 * 
		 */		
		private function isOpen(findPathNode:FindPathNode):Boolean
		{
			for each(var node:FindPathNode in _openNodes)
			{
				if(findPathNode==node)return true;
			}
			return false;
		}
		
		/**
		 *是否在已考察列表里面
		 * @param findPathNode
		 * @return 
		 * 
		 */		
		private function isClosed(findPathNode:FindPathNode):Boolean
		{
			for each(var node:FindPathNode in _closedNodes)
			{
				if(findPathNode==node)return true;
			}
			return false;
		}
		
		/**
		 *根据单元格取得寻路网络节点
		 * @param findPathCell 单元格
		 * @return 如果能取到返回寻路网络节点，否则返回null
		 * 
		 */		
		private function getFindPathNodeByCell(findPathCell:FindPathCell):FindPathNode
		{
			for each(var findPathNode:FindPathNode in _findPathNodes)
			{
				if(findPathCell.x>=findPathNode.x
					&& findPathCell.x<findPathNode.x+findPathNode.width
					&& findPathCell.y>=findPathNode.y
					&& findPathCell.y<findPathNode.y+findPathNode.height
				)
				{
					return findPathNode;
				}
			}
			return null;
		}
		
		public function dispose():void
		{
			_findPathNodes=null;
		}

		/**
		 *寻到的的路径点列表
		 */
		public function get path():Vector.<Point>
		{
			return _path;
		}

		/**
		 *已经寻到的导航网格集 
		 */
		public function get findPaths():Vector.<FindPathNode>
		{
			return _findPaths;
		}
	}
}